/*
https://leetcode-cn.com/problems/minimum-absolute-sum-difference/solution/jue-dui-chai-zhi-he-by-leetcode-solution-gv78/
 */
import java.util.Arrays;

public class Solution1818 {

    private static final int mod = 1000000007;

    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int[] f= Arrays.copyOf(nums1,nums1.length);
        Arrays.sort(f);
        int max=0;
        int sum=0;
        for (int i=0;i<nums1.length;i++){
            sum=(sum+Math.abs(nums1[i]-nums2[i]))%mod;
            int l=0,r=nums1.length-1;
            int target=-1;
            while (l<r){
                int mid=(l+r)/2;
                if (f[mid]>=nums2[i]){
                    r=mid;
                }else{
                    l=mid+1;
                }
                if (r-l==1){
                    if (nums2[i]>f[l]){
                        target=r;
                    }else{
                        target=l;
                    }
                    break;
                }
            }
            if (l==r){
                target=l;
            }
            int min=Math.abs(f[target]-nums2[i]);
            if (target>0){
                min=Math.min(min,Math.abs(f[target-1]-nums2[i]));
            }
            max=Math.max(max,Math.abs(nums1[i]-nums2[i])-min);
        }
        return ((sum-max)%mod+mod)%mod;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1818().minAbsoluteSumDiff(new int[]{1,7,5},new int[]{2,3,5}));
    }
}
